package com.wang.sort;

import java.util.PriorityQueue;
//已知一个几乎有序的数组，几乎有序：如果把数组排序，每个元素移动的距离不超过k，k相对于数组长度来说较小
public class Demo21_SortArrayDistanceLessK {
    public void sortedArrDistanceLessK(int[] arr, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int index = 0;
        for (; index <= Math.min(arr.length - 1, k) ; index++) {
            heap.add(arr[index]);
        }
        int i = 0;
        for (; i < arr.length ; i++, index++) {
            heap.add(arr[index]);
            arr[i] = heap.poll();
        }
        while (!heap.isEmpty()) {
            arr[i++] = heap.poll();
        }
    }
}
